package com.practice.zuocy.base.class07;

import java.util.Stack;

/**
 * （1）非递归方法实现：二叉树的先序、中序、后序遍历
 */
public class Code02_UnRecursiveTraversalBT {

	/**
	 * 二叉树的节点结构
	 */
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int v) {
			value = v;
		}
	}

	/**
	 * 非递归实现先序遍历（使用一个栈）
	 *
	 * @param head 当前节点
	 */
	public static void pre(Node head) {
		System.out.print("pre-order: ");
		if (head != null) {
			Stack<Node> stack = new Stack<Node>();
			// 1. 当前节点进栈
			stack.add(head);
			// 2. 栈不为空时：
			while (!stack.isEmpty()) {
				// 2.1 弹出一个节点并且打印
				head = stack.pop();
				System.out.print(head.value + " ");
				if (head.right != null) {
					// 2.2 弹出的节点有右孩子，则右孩子进栈
					stack.push(head.right);
				}
				if (head.left != null) {
					// 2.3 弹出的节点有左孩子，则左孩子进栈
					stack.push(head.left);
				}
			}
		}
		System.out.println();
	}

	/**
	 * 非递归实现中序遍历（使用一个栈）
	 *
	 * @param head 当前节点
	 */
	public static void in(Node head) {
		System.out.print("in-order: ");
		if (head != null) {
			Stack<Node> stack = new Stack<Node>();
			// 1. 栈不为空或者当前节点不为空时
			while (!stack.isEmpty() || head != null) {
				if (head != null) {
					// 1.1.1 当前节点不为空，当前节点进栈
					stack.push(head);
					// 1.1.2 当前节点来到左孩子处
					head = head.left;
				} else {
					// 1.2.1 当前节点为空，弹出一个节点，并且打印
					head = stack.pop();
					System.out.print(head.value + " ");
					// 1.2.2 当前节点来到右孩子处
					head = head.right;
				}
			}
		}
		System.out.println();
	}

	/**
	 * 非递归实现后序遍历（使用两个栈）
	 *
	 * @param head 当前节点
	 */
	public static void pos1(Node head) {
		System.out.print("pos-order: ");
		if (head != null) {
			Stack<Node> s1 = new Stack<Node>();
			// 辅助用
			Stack<Node> s2 = new Stack<Node>();
			// 1. 当前节点进栈
			s1.push(head);
			// 2. 栈不为空时：
			while (!s1.isEmpty()) {
				// 2.1 弹出一个节点并且进辅助栈
				head = s1.pop();
				s2.push(head);
				if (head.left != null) {
					// 2.2 弹出的节点有左孩子，则左孩子进栈
					s1.push(head.left);
				}
				if (head.right != null) {
					// 2.3 弹出的节点有右孩子，则右孩子进栈
					s1.push(head.right);
				}
			}
			while (!s2.isEmpty()) {
				System.out.print(s2.pop().value + " ");
			}
		}
		System.out.println();
	}

	/**
	 * 非递归实现后续遍历（使用一个栈）
	 *
	 * @param h 当前节点
	 */
	public static void pos2(Node h) {
		System.out.print("pos-order: ");
		if (h != null) {
			Stack<Node> stack = new Stack<Node>();
			stack.push(h);
			// c用来跟踪栈顶
			Node c = null;
			while (!stack.isEmpty()) {
				c = stack.peek();
				if (c.left != null && h != c.left && h != c.right) {
					// 有左树，并且左树没有处理过时，处理左树（压栈）
					stack.push(c.left);
				} else if (c.right != null && h != c.right) {
					// 有右树，并且右树没有处理过时，处理右树（压栈）
					stack.push(c.right);
				} else {
					// 左右两个子树都处理完了或者没有左右子树时，处理自己（弹出、打印）
					System.out.print(stack.pop().value + " ");
					// h用来跟踪打印的节点
					h = c;
				}
			}
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Node head = new Node(1);
		head.left = new Node(2);
		head.right = new Node(3);
		head.left.left = new Node(4);
		head.left.right = new Node(5);
		head.right.left = new Node(6);
		head.right.right = new Node(7);

		pre(head);
		System.out.println("========");
		in(head);
		System.out.println("========");
		pos1(head);
		System.out.println("========");
		pos2(head);
		System.out.println("========");
	}

}
